#include "list.h"

ListNode *BuyListNode(LTDataType x)
{
    //创建新节点
    ListNode *newnode = (ListNode *)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    else
    {
        newnode->val = x;
        newnode->next = NULL;
        newnode->prev = NULL;
    }
    return newnode;
}

ListNode *ListInit()
{
    //创建哨兵位头节点
    ListNode *phead = BuyListNode(0);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

void ListPrint(ListNode *phead)
{
    assert(phead);
    ListNode *cur = phead->next;
    //当cur为phead时，说明已走完一遍
    while (cur != phead)
    {
        printf("%d->", cur->val);
        cur = cur->next;
    }
    printf("phead\n");
}

void ListPushBack(ListNode *phead, LTDataType x)
{
    assert(phead);
    ListNode *newnode = BuyListNode(x);
    ListNode *tail = phead->prev;

    tail->next = newnode;
    newnode->prev = tail;

    newnode->next = phead;
    phead->prev = newnode;
}

void ListPopBack(ListNode *phead)
{
    assert(phead);
    //当删到只有哨兵位时，哨兵位前驱后驱都指向自己，这时就不能再删了
    assert(phead->prev != phead);

    ListNode *tailPrev = phead->prev->prev;
    free(phead->prev);
    tailPrev->next = phead;
    phead->prev = tailPrev;
}

void ListPushFront(ListNode *phead, LTDataType x)
{
    assert(phead);
    ListNode *newnode = BuyListNode(x);
    ListNode *next = phead->next;

    newnode->next = next;
    next->prev = newnode;

    phead->next = newnode;
    newnode->prev = phead;
}

void ListPopFront(ListNode *phead)
{
    assert(phead);
    //当删到只有哨兵位时，哨兵位前驱后驱都指向自己，这时就不能再删了
    assert(phead->prev != phead);
    ListNode *head = phead->next;
    ListNode *next = phead->next->next;
    if (head->next == NULL)
    {
        free(head);
        phead->next = phead;
        phead->prev = phead;
    }
    else
    {
        free(phead->next);
        phead->next = next;
        next->prev = phead;
    }
}

ListNode *ListFind(ListNode *phead, LTDataType x)
{
    ListNode *cur = phead->next;
    //当cur为phead时，说明已走完一遍
    while (cur != phead)
    {
        if (cur->val == x)
        {
            //找到返回这个值得节点地址
            return cur;
        }
        cur = cur->next;
    }
    //没找到返回空指针
    return NULL;
}

void ListInsert(ListNode *pos, LTDataType x)
{
    //这里不用判空
    ListNode *newnode = BuyListNode(x);
    ListNode *posPrev = pos->prev;
    //这里必须先链接newnode后面的节点,先链接前面的节点会找不到下一个节点
    newnode->next = pos;
    pos->prev = newnode;

    posPrev->next = newnode;
    newnode->prev = posPrev;
}

void ListErase(ListNode *pos)
{
    ListNode *posPrev = pos->prev;
    ListNode *posNext = pos->next;
    free(pos);
    posPrev->next = posNext;
    posNext->prev = posPrev;
}

void ListDestory(ListNode *head)
{
    assert(head);
    ListNode *cur = head->next;
    while (cur != head)
    {
        ListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    free(head);
}

int main()
{
    //测试

    //尾插
    ListNode *phead = ListInit();
    ListPushBack(phead, 1);
    ListPushBack(phead, 2);
    ListPushBack(phead, 3);
    ListPushBack(phead, 4);
    ListPushBack(phead, 5);
    ListPushBack(phead, 6);

    ListPrint(phead);

    //尾删
    ListPopBack(phead);
    ListPopBack(phead);
    ListPrint(phead);

    //头插
    ListPushFront(phead, 0);
    ListPushFront(phead, -1);
    ListPushFront(phead, -2);
    ListPrint(phead);

    //头删
    ListPopFront(phead);
    ListPopFront(phead);
    ListPopFront(phead);
    ListPrint(phead);

    //在pos后面插入新节点
    ListNode *pos = ListFind(phead, 2);
    if (pos)
        ListInsert(pos, 100);
    else
        printf("Don't find.....\n");
    ListPrint(phead);

    //删除pos位置的节点
    ListNode *pos2 = ListFind(phead, 2);
    if (pos)
        ListErase(pos2);
    else
        printf("Don't find.....\n");
    ListPrint(phead);
    ListDestory(phead);
    system("pause");
    return 0;
}